An execution of a distributed algorithm is a game between the algorithm andan adversary causing distractions to the computation. In this work we define aclass of ordered adversaries causing distractions according to some partialorder fixed by the adversary before the execution, and study how they affectperformance of algorithms. We focus on Do-All problem of performing t tasks ona shared channel consisting of p crash-prone stations. The channel restrictscommunication: no message is delivered to the alive stations if more than onestation transmits at the same time. The performance measure for Do-All problemis work: the total number of available processor steps during the wholeexecution. We address the question of how the ordered adversaries controllingcrashes of stations influence work performance of Do-All algorithms. The firstpresented algorithm solves Do-All with work O(t+p\sqrt{t}\log p) against theLinearly-Ordered adversary, restricted by some pre-defined linear order ofcrashing stations. Another algorithm runs against the Weakly-Adaptiveadversary, restricted by some pre-defined set of f crash-prone stations (it canbe seen as restricted by the order being an anti-chain of crashing stations).The work done by this algorithm is O(t+p\sqrt{t}+p\min{p/(p-f),t}\log p). Bothresults are close to the corresponding lower bounds from [CKL]. We generalizethis result to the class of adversaries restricted by partial order of maximumanti-chain of size k and complementary lower bound. We also consider a class ofdelayed adaptive adversaries, who could see random choices with some delay. Wegive an algorithm that runs against the 1-RD adversary (seeing random choicesof stations with one round delay), achieving close to optimalO(t+p\sqrt{t}\log^2 p) work complexity. This shows that restricting adversaryby even 1 round delay results in (almost) optimal work on a shared channel.
展开▼
机译：分布式算法的执行是算法与对手之间的博弈，导致计算分心。在这项工作中，我们根据执行前对手确定的部分偏序来定义一类造成干扰的有序对手，并研究它们如何影响算法的性能。我们关注在由p个易于崩溃的站点组成的共享通道上执行t任务的全能问题。信道限制了通信：如果同时发送多个站，则没有消息传递到活动的站。 “解决所有问题”的性能度量有效：整个执行过程中可用处理器步骤的总数。我们解决的问题是，控制站点崩溃的有序对手如何影响“全通”算法的工作性能。第一个提出的算法针对线性排序的对手（受某些预定义的碰撞站线性顺序限制），用工作O（t + p \ sqrt {t} \ log p）求解“全部”。另一种算法针对弱自适应对手，它受一组预定义的f个易于发生碰撞的站点的限制（可以看作是受碰撞站点的反链顺序限制），该算法完成的工作是O（ t + p \ sqrt {t} + p \ min {p /（pf），t} \ log p）。两种结果均接近[CKL]的相应下限。我们将此结果推广到受大小为k的最大反链和互补下界的偏序限制的对手类别。我们还考虑了一类延迟的适应性对手，他们可能会看到随机选择并稍有延迟。否定一种针对1-RD对手的算法（看到具有一轮延迟的随机选择站），从而达到接近最佳O（t + p \ sqrt {t} \ log ^ 2 p）的工作复杂度。这表明将对手限制甚至1轮延迟都会导致（几乎）在共享渠道上的最佳工作。
展开▼
